# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        """哈希表
        两次循环，第一次复制链表，保存新旧结点映射，第二次复制random
        """
        if head is None:
            return None
        
        # 将旧结点映射到新结点上
        record = dict() 
        
        # 头结点
        res = Node(head.val)
        record[head] = res
        
        # 顺序复制链表
        p, q = head.next, res
        while p is not None:
            q.next = Node(p.val)
            record[p] = q.next
            q, p = q.next, p.next
        
        # 顺序复制random
        p, q = head, res
        while p is not None:
            if p.random is not None: # 注意random指向None
                q.random = record[p.random]
            q, p = q.next, p.next
        
        return res
